package developer.算法.回溯.全排列;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/4/1 11:19
 * @description 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 1 2 3
 * 1 3 2
 * 2 1 3
 * 2 3 1
 * 3 2 1
 * 3 1 2
 * <p>
 * 1 2 3 4
 * 1 2 4 3
 * 1 3 2 4
 * 1 3 4 2
 *
 * <p>
 * <p>
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 * <p>
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 * <p>
 * 输入：nums = [1]
 * 输出：[[1]]
 * <p>
 * <p>
 * 1 2 3
 * 2 1 3
 * 3 2 1
 * <p>
 * 1 3 2
 * 2 3 1
 * 3 1 2
 */
public class QuanPaiLie {
    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        List<List<Integer>> permute = solution.permute(
                new int[]{1, 2, 3}
        );

        for (List<Integer> integers : permute) {
            System.out.println();
            integers.forEach(System.out::print);
        }

    }

    static class Solution4 {
        List<List<Integer>> result;

        public List<List<Integer>> permute(int[] nums) {
            result = new ArrayList<>();
            List<Integer> total = new ArrayList<>();
            for (int num : nums) {
                total.add(num);
            }
            dfs(0, nums.length, total);
            return result;
        }

        private void dfs(int start, int end, List<Integer> total) {
            if (start == end - 1) {
                result.add(new ArrayList<>(total));
                return;
            }
            for (int i = start; i < end; i++) {
                Collections.swap(total, i, start);
                dfs(start + 1, end, total);
                Collections.swap(total, i, start);
            }
        }

    }


    static class Solution3 {
        private List<List<Integer>> result;

        public List<List<Integer>> permute(int[] nums) {
            result = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            dfs(nums.length, list, 0);
            return result;
        }

        private void dfs(int end, List<Integer> nums, int first) {
            if (first == end - 1) {//只有递归到最后一层的时候才需要保存数据 详情见png
                result.add(new ArrayList<>(nums));
            }
            for (int i = first; i < end; i++) {
                Collections.swap(nums, first, i);
                dfs(end, nums, first + 1);//维护这个first是关键
                Collections.swap(nums, first, i);
            }
        }


    }

    static class Solution {
        public List<List<Integer>> permute(int[] nums) {

            List<List<Integer>> res = new ArrayList<>();
            back(0, nums.length, nums, res);
            return res;
        }

        public void back(int start, int end, int[] nums, List<List<Integer>> result) {
            if (start == end) {//start==end 说明交换全部完成了 加入结果
                result.add(toList(nums));
            }

            for (int i = start; i < end; i++) {
                swap(nums, start, i);//交换目标位置
                back(start + 1, end, nums, result);
                swap(nums, start, i);//还原
            }
        }

        private int[] swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            return nums;
        }

        private List<Integer> toList(int[] nums) {
            List<Integer> single = new ArrayList<>();
            for (int num : nums) {
                single.add(num);
            }
            return single;
        }

    }


    class SolutionOfficial {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();

            List<Integer> output = new ArrayList<Integer>();
            for (int num : nums) {
                output.add(num);
            }

            int n = nums.length;
            backtrack(n, output, res, 0);
            return res;
        }

        //回溯
        public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
            // 所有数都填完了
            if (first == n) {
                res.add(new ArrayList<Integer>(output));
            }
            for (int i = first; i < n; i++) {
                // 动态维护数组
                Collections.swap(output, first, i);
                // 继续递归填下一个数
                backtrack(n, output, res, first + 1);
                // 撤销操作
                Collections.swap(output, first, i);
            }
        }
    }

}
